The present invention is generally directed to a carry-out generator for addition of two positive numbers.
Binary addition operates on an augend and an addend, both of which may include a series of registers having a bit of either unity (=1) or zero (=0). A full adder of two bits combines two bits to find a sum. The addition may be evaluated for a bit register of any length. A carry-in may be received from the adjacent lesser bit register, and the result may detect a carry-out to be received by the adjacent greater bit register. The full adder for bit register receives an augend input A, an addend input B, a carry-in input Ci. The results from the adder include a sum S and a carry-out Co. FIG. 1 illustrates an adder as a block diagram featuring the inputs and outputs. The adder 10 receives an augend 12, an addend 14 and a carry-in 16. The outputs include a sum 18 and a carry-out 20.
The results S and Co depend on the input values. In FIG. 2, a logic table shows row of inputs and corresponding outputs for a bit register. The legend 22 identifies the inputs A (augend), B (addend), and Ci (carry-in), along with the possible outputs S (sum) and Co (carry-out). The first four rows 24, 26, 28 and 30 are shown for no carry-in bit, while the last four rows 32, 34, 36 and 38 are shown for a carry-in bit. The carry-out propagation can be time-consuming for a processor. Various schemes to reduce the propagation time have been developed, including look-ahead carry chain.
In many applications, such as a control shift for a multiplexer or a conditional branch, only the carry-out is required. In such circumstances, calculating the addition of the augend and addend to obtain the sum bit and the cascading carry-out bit needlessly consumes processing time. A solution is desired to expedite the carry-out result without an adder.
A carry-out bit generator determines if a bit pattern from two positive numbers matches one of the patterns for which a carry-out bit would be generated in addition. These patterns include a TnG pattern and a Tm pattern (with a carry-in). Superscript n represents a number between zero and mxe2x88x921, superscript m represents the number of registers, T represents a 0/1 or 1/0 pair and G represents a 1/1 pair.